package com.zzz.offer.fabonacci;

import java.util.HashMap;
import java.util.Map;

public class FibonacciSum {
    Map<String, Integer> map = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(new FibonacciSum().fibonacci2(6));

    }

    // 递归方式
    public int fibonacci(int n) {

        if (n == 0) {
            return 0;
        }

        if (n == 1 || n == 2) {
            return 1;
        }

        int fn1 = map.get(String.valueOf(n - 1)) == null ? 0 : map.get(String.valueOf(n - 1));
        int fn2 = map.get(String.valueOf(n - 2)) == null ? 0 : map.get(String.valueOf(n - 2));

        int sum;

        if (fn1 > 0 && fn2 > 0) {
            sum = fn2 + fn1;
        } else if (fn1 > 0) {
            sum = fn1 + fibonacci(n - 2);
        } else if (fn2 > 0) {
            sum = fibonacci(n - 1) + fn2;
        } else {
            sum = fibonacci(n - 1) + fibonacci(n - 2);
        }

        map.put(String.valueOf(n), sum);
        return sum;
    }

    // 大为震撼
    public int fibonacci1(int n) {
        int a = 1;
        int b = 1;
        int c = 1;
        if (n == 0) {
            return 0;
        }
        if (n < 3) {
            return 1;
        }

        for (int i = 2; i <= n; i++) {
            b = c;
            a = c - a;
            c = a + b;
        }
        return c;
    }

    public int fibonacci2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int fn = 1;
        int fn1 = 1;
        int fn2 = 1;


        for (int i = 2; i < n; i++) {
            fn = fn1 + fn2;
            fn2 = fn1;
            fn1 = fn;
        }
        return fn;
    }
}
